package com.yun.datastructure.tree.binarysearchtree.leetcode;

import com.yun.datastructure.tree.binarytree.domain.TreeNode;

public class Leetcode450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        root=doDelete(root,key);
        return root;
    }

    private TreeNode doDelete(TreeNode node,int key){
        if(node==null){
            return null;
        }
        if(key<node.val){
            node.left=doDelete(node.left,key);
            return node;
        }
        if(node.val<key){
            node.right=doDelete(node.right,key);
            return node;
        }
        //找到被删除节点
        //情况1：被删除节点只有左孩子
        if(node.right==null){
            return node.left;
        }
        //情况2：被删除节点只有右孩子
        if(node.left==null){
            return node.right;
        }
        //情况3：被删除节点同时有左孩子和右孩子
        TreeNode s=node.right;
        while (s.left!=null){
            s=s.left;
        }
        s.right=doDelete(node.right,s.val);
        s.left=node.left;
        return s;
    }
}
